Solving 10385 - Duathlon (Ternary search)
[andmenj-acm.git] / 12322 - Handgun Shooting Sport / 12322.3.cpp
bloba440b3f3f4fc078fbefdfd169d48dba64fb424ed
1 // Accepted, trying to make it run faster.
2 using namespace std;
3 #include <algorithm>
4 #include <iostream>
5 #include <iterator>
6 #include <numeric>
7 #include <sstream>
8 #include <fstream>
9 #include <cassert>
10 #include <climits>
11 #include <cstdlib>
12 #include <cstring>
13 #include <bitset>
14 #include <string>
15 #include <cstdio>
16 #include <vector>
17 #include <cmath>
18 #include <queue>
19 #include <deque>
20 #include <stack>
21 #include <list>
22 #include <map>
23 #include <set>
25 #define foreach(x, v) for (typeof (v).begin() x=(v).begin(); x !=(v).end(); ++x)
26 #define For(i, a, b) for (int i=(a); i<(b); ++i)
27 #define D(x) cout << #x " is " << x << endl
29 namespace IO {
30 #define MAXBUFF (1<<20)
31 char buffer[MAXBUFF], *p = buffer+MAXBUFF;
32 char buffer2[MAXBUFF], *p2 = buffer2;
34 inline char read_char() {
35 if( p == buffer+MAXBUFF ) {
36 fread( buffer, 1, MAXBUFF, stdin );
37 p = buffer;
39 return *p++;
42 inline int read_int() {
43 char c = read_char();
44 while( !isdigit(c) and c != '-' ) c = read_char();
45 int sign = c == '-' ? -1 : +1;
46 if (c == '-') c = read_char();
47 int ret = c-'0';
48 while( isdigit(c = read_char()) ) ret = ret * 10 + c-'0';
49 return ret * sign;
52 void flush() {
53 fwrite( buffer2, 1, p2-buffer2, stdout );
54 p2 = buffer2;
57 inline void write( char c ) {
58 if( p2 == buffer2+MAXBUFF ) {
59 fwrite( buffer2, 1, MAXBUFF, stdout );
60 p2 = buffer2;
62 *p2++ = c;
66 struct point {
67 int x, y;
68 point(){} point(int x, int y) : x(x), y(y) {}
69 bool operator < (const point &t) const {
70 return x * t.y - y * t.x > 0;
72 bool operator == (const point &t) const {
73 return x * t.y - y * t.x == 0;
75 bool operator <= (const point &t) const {
76 return *this < t or *this == t;
78 bool operator != (const point &t) const {
79 return !(*this == t);
83 typedef pair< point, point > interval;
85 // Returns true if interval 'a' is strictly included in interval 'b'
86 inline bool included(const interval &a, const interval &b) {
87 return b.first < a.first and a.second < b.second;
90 const int MAXN = 1001;
92 interval intervals[MAXN];
93 int B;
95 inline void delete_redundant() {
96 bitset<MAXN> deleted;
97 for (int i = 0; i < B; ++i) {
98 for (int j = 0; j < B; ++j) {
99 // delete interval i if interval j is completely inside it
100 if (included(intervals[j], intervals[i])) {
101 deleted[i] = true;
102 break;
106 int k = 0;
107 for (int i = 0; i < B; ++i) {
108 if (!deleted[i]) {
109 intervals[k++] = intervals[i];
112 B = k;
115 char buf[10];
117 int main(){
118 while (B = IO::read_int()) {
119 for (int i = 0; i < B; ++i) {
120 point p1, p2;
121 intervals[i].first.x = IO::read_int();
122 intervals[i].first.y = IO::read_int();
123 intervals[i].second.x = IO::read_int();
124 intervals[i].second.y = IO::read_int();
125 if (intervals[i].second < intervals[i].first) swap(intervals[i].first, intervals[i].second);
127 //printf("Before removing redundant B is %d\n", B);
128 delete_redundant();
129 sort(intervals, intervals + B);
130 //printf("After removing redundant B is %d\n", B);
132 //printf("Before removing duplicates B is %d\n", B);
133 B = unique(intervals, intervals + B) - intervals;
134 //printf("After removing duplicates B is %d\n", B);
136 int ans = 0, i = 0;
137 while (i < B) {
138 ans++;
139 point pick = intervals[i].second;
140 while (i < B and intervals[i].first <= pick) i++;
142 sprintf(buf, "%d\n", ans);
143 for (char * c = buf; *c; ++c) IO::write(*c);
145 IO::flush();
146 return 0;